Recursive Functions

A definition that defines an object in terms of itself is said to be recursive. In computer science, recursion refers to a function or subroutine that calls itself, and it is a fundamental paradigm in programming. A recursive program is used for solving problems that can be broken down into sub-problems of the same type, doing so until the problem is easy enough to solve directly.

Examples

Fibonacci Numbers

A common recursive function that you’ve probably encountered is the Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, and so on. That is, you get the next Fibonacci number by adding together the previous two. Mathematically, this is written as

f(N)=f(N-1)+f(N-2)

Try finding f(10). No doubt, you have the correct answer, because you intuitively stopped when you reach f(1) and f(0). To be formal about this, we need to define when the recursion stops, called the base cases . The base cases for the Fibonacci function is f(0)=0, and f(1)=1. The typical way to write this function is as follows:

$f(N)=\{\begin{array}{cc}N& (N\le 1)\\ f(N-1)+f(N-2)& (N>1)\end{array}$

Here is a Python implementation of the Fibonacci function:

def Fibonacci(x):
  if (x <= 1) return x
  return Fibonacci(x-1) + Fibonacci(x-2)

(As a challenge to the reader: How could you implement the Fibonacci function without using recursion?)

Factorial Function

Consider the factorial function, n!=n*(n−1)*...*1, with 0! defined as having a value of 1. We can define this recursively as follows:

$f(x)=\{\begin{array}{cc}1& (x=0)\\ x\ast f(x-1)& (x>1)\end{array}$

With this definition, the factorial of every non-negative integer can be found.

Here is a Python implementation of the factorial function:

def Factorial(x):
  if (x == 0) return 1
  return x * Factorial(x-1)

Some Definitions

A few definitions: Indirection recursion is when a function calls another function which eventually calls the original function.

For example, A calls B, and then, before function B exits, function A is called (either by B or by a function that B calls).

• Single recursion is recursion with a single reference to itself, such as the factorial example above.

• Multiple recursion , illustrated by the Fibonacci number function, is when a function has multiple self references.

• Infinite recursion is a recursive function that never returns because it keeps calling itself. The program will eventually crash with an out of memory error message of some sort.

This ACSL category focuses on mathematical recursive functions rather than programming algorithms.

While many mathematical functions can be done iteratively more efficiently than they can be done recursively, many algorithms in computer science must be written recursively.

The Tower of Hanoi which is referred to in one of the videos is a good example of this. Another example is given in the sample problems below.

Sample Problems

This ACSL category focuses on mathematical recursive functions rather than programming procedures; but you’ll see some of the latter. You will typically be asked to evaluate a recursive function for some specific value.

It's important that you are careful and neat. Work your way down the recursive calls until there are no more calls, and then work your way back up.

Recursive Function

Find g(11) given the following

$$g(x)=\{\begin{array}{cc}g(x-3)+1& (x>0)\\ 3x& (otherwise)\end{array}$$

g(11) =

[0/2]

Recursive Function

Find the value of h(13) given the following definition of h:

$$h(x)=\{\begin{array}{cc}h(x-7)+1& (x>5)\\ x& (0\le x\le 5)\\ h(x+3)& (x\le 0)\end{array}$$

h(13) =

[0/2]

Recursive Function

Find the value of f(12,6) given the following definition of f:

$$f(x,y)=\{\begin{array}{cc}f(x-y,y-1)+2& (x>y)\\ x+y& (otherwise)\end{array}$$

f(12,6) =

[0/2]

Recursive Function

Consider the following recursive algorithm for painting a square:

1. Given a square.
2. If the length of a side is less than 2 feet, then stop.
3. Divide the square into 4 equal size squares (i.e., draw a “plus” sign inside the square).
4. Paint one of these 4 small squares.
5. Repeat this procedure (start at step 1) for each of the 3 unpainted squares.

If this algorithm is applied to a square with a side of 16 feet (having a total area of 256 sq. feet), how many square feet will be painted?

[0/2]